package LearnAlgorithm.i_递归进阶andDFSand剪枝and回溯;

/*
有一个X*Y的网格，1个机器人只能走1个格子，且只能向右或向下走，要从左上角走到右下角。
请设计一个算法，计算机器人有多少种走法。
给定两个正整数int x, int y,请返回机器人的走法数目。
保证x + y <= 12

 */
public class b机器人走方格 {
	/**
	 * TODO 讲个笑话：人理解迭代；神理解递归。
	 * @param args
	 */
	public static void main(String[] args) {
		long time1 = System.currentTimeMillis();
		System.out.println(recursion1(15,15));
		util.Util.duration(time1);
		long time2 = System.currentTimeMillis();
		System.out.println(recursion2(100,100));
		util.Util.duration(time2);
	}
	
	/**
	 * 递归形式 
	 * O(2^N)
	 * @param x
	 * @param y
	 * @return
	 */
	public static long recursion1(int x, int y) {
		if (x == 1 || y == 1) {
			return 1;
		}
		return recursion1(x - 1, y) + recursion1(x, y - 1);
	}
	
	/**
	 * 迭代形式
	 * DP公式：f(x, y) = f(x-1, y) + f(x, y-1)
 	0	1	2	3	4	5	6(n+1)	列下标[n + 1] n=5
0	0	0	0	0	0	0

1	0	1	1	1	1	1

2	0	1	2	3	4	5

3	0	1	3	6	10	15

4	0	1	4	10	20	35

5	0	1	5	15	35	70

6(n+1)
行下标[n + 1] n=5

		O(N^2)
	 * @param m
	 * @param n
	 * @return
	 */
	public static long recursion2(int m, int n) {
		long[][] status = new long[m + 1][n + 1];//令下标有意义；所以才+1
		for (int i = 1; i < n + 1; i++) {//status[0][i]全为1
			status[1][i] = 1;
		}
		for (int j = 1; j < m + 1; j++) {//status[j][0]全为1
			status[j][1] = 1;
		}
		for (int k = 2; k < m + 1; k++) {
			for (int l = 2; l < n + 1; l++) {
				status[k][l] = status[k][l - 1] + status[k - 1][l];
			}
		}
		return status[m][n];
	}
}
